#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.


"""
    二分法: 数组走势如下图

    /
   /
  /
 /
/

         /
        /
       /
      /
     /

"""
class Solution:
    """
    @param nums: a rotated sorted array
    @return: the minimum number in the array
    """
    # def findMin(self, nums):
    #     # write your code here
    #     left, right = 0, len(nums) - 1
    #     while left < right:
    #         mid = (left + right) // 2
    #         print(left, mid, right)
    #         if nums[mid] > nums[right]:
    #             left = mid + 1
    #         elif nums[mid] < nums[right]:
    #             right = mid
    #         else:
    #             assert nums[mid] == nums[right]
    #             if nums[mid] != nums[left]:
    #                 assert nums[mid] < nums[left]
    #                 right = mid
    #             else:
    #                 # 二分后继续

    #     print(right)
    #     return nums[right]

    def findMin(self, nums):
        if not nums:
            return -1
        idx, value = self.rec_find(nums, 0, len(nums) - 1)
        return idx

    def rec_find(self, nums, left, right):
        assert left <= right
        if left == right:
            return left, nums[left]

        mid = (left + right) // 2
        print(left, mid, right)
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            assert nums[mid] == nums[right]
            if nums[mid] != nums[left]:
                assert nums[mid] < nums[left]
                right = mid
            else:
                idx1, value1 = self.rec_find(nums, left, mid)
                idx2, value2 = self.rec_find(nums, mid+1, right)
                if value1 > value2:
                    return idx2, value2
                else:
                    return idx1, value1

        return self.rec_find(nums, left, right)


def main():
    print("start main")
    s = Solution()
    # ret = s.findMin([4,5,6,7,8,9,1, 1, 1,2,3])
    # ret = s.findMin([7, 0, 1, 1, 1,2,3])
    # ret = s.findMin([0, 1, 1, 1,2,3])
    # ret = s.findMin([2, 1, 1, 1, 1, 1])
    # ret = s.findMin([4,4,4,5,1,4])
    # ret = s.findMin([])
    ret = s.findMin([1,1,3,1])
    print(ret)

if __name__ == "__main__":
    main()
